package com.sunny.l40;

public class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(null == head)
            return null;
        return dfs(head);
    }

    public TreeNode dfs(ListNode head){
        int num = 0;
        ListNode node = head;
        while (null != node){
            num++;
            node = node.next;
        }
        if(1 == num){
            return new TreeNode(head.val);
        }
        if(2 == num){
            TreeNode ret = new TreeNode(head.next.val);
            ret.left = new TreeNode(head.val);
            return ret;
        }
        int step = (num+2)>>1;
        ListNode prev = head;
        node = prev.next;
        step -= 2;
        while (step-->0){
            prev = node;
            node = node.next;
        }
        prev.next = null;
        TreeNode root = new TreeNode(node.val);
        root.left = dfs(head);
        root.right = dfs(node.next);
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}